package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.3 MB, 在所有 Go 提交中击败了81.05%的用户
 */
func isMatch(s string, p string) bool {
	n, m := len(s), len(p)
	s, p = " "+s, " "+p

	f := make([][]bool, n+1)
	for i := 0; i < n+1; i++ {
		f[i] = make([]bool, m+1)
	}

	f[0][0] = true
	for i := 0; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if j+1 <= m && p[j+1] == '*' { continue }
			if i > 0 && p[j] != '*' {
				f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.')
			} else if p[j] == '*' {
				f[i][j] = f[i][j - 2] || (i > 0 && f[i - 1][j] &&  (s[i] == p[j - 1] || p[j - 1] == '.'))
			}
		}
	}
	return f[n][m]
}

func main() {
	fmt.Println(isMatch("aa", "a"))  // false
	fmt.Println(isMatch("aa", "a*"))  // true
}
